/**
 *
 *
 * Date: 2022-09-30
 * Time: 22:55
 */
public class Algorithm {
    /*
    public ListNode Merge(ListNode list1,ListNode list2) {
        // // 1. 一个一个的比较然后合并
        // ListNode head = new ListNode(-1); //新建一个节点作为合并链表的头
        // ListNode tail = head; // 永远指向合并链表的头节点.

        // while(list1 != null && list2 != null) {
        //     if(list1.val < list2.val) {
        //         tail.next = list1;
        //         list1 = list1.next;
        //     } else {
        //         tail.next = list2;
        //         list2 = list2.next;
        //     }
        //     tail = tail.next;
        // }
        // // 走到这要么list1 == null 要么list2 == null
        // if(list1 == null) {
        //     tail.next = list2;
        // } else {
        //     tail.next = list1;
        // }
        // return head.next;


        // 2. 利用递归

        if(list1 == null) { return list2; }
        if(list2 == null) { return list1; }

        ListNode head = null;

        if(list1.val < list2.val) {
            head = list1;
            list1 = list1.next;
        } else {
            head = list2;
            list2 = list2.next;
        }

        head.next = Merge(list1,list2);

        return head;
    }

     */
}
